from typing import List
"""
    给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，
    且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

    示例 1：
        输入：n = 3
        输出：[[1,2,3],[8,9,4],[7,6,5]]
"""

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        a = [[0] * n for _ in range(n)]
        tem = 1
        for i in range(n):
            # i 是遍历的圈数
            for j in range(i,n - i - 1):
                a[i][j] = tem
                a[j][n-1-i] = tem + (n - 1 - 2*i)
                a[n-1-i][n-1-j] = tem + 2 *(n - 1 -2*i)
                a[n-1-j][i] = tem + 3 *(n - 1 -2*i)
                tem += 1
            tem += 3 * (n - 1 - 2 * i)

        if n % 2 == 1:
            a[n//2][n//2] = n * n

        return a